#include <stdlib.h>
#include "BST.h"

Node *createNode(int x) {
  Node *newNode = (Node*)malloc(sizeof(Node));
  newNode->key = x;
  newNode->left = newNode->right = NULL;
  return newNode;
}

// See slide 26, chapter 8
Node *insertNode(Node **proot, int x) {
  if(*proot == NULL) {
    return *proot = createNode(x);
  }
  if((*proot)->key == x) {
    return NULL;
  }
  if((*proot)->key > x) {
    return insertNode(&(*proot)->left, x);
  } else {
    return insertNode(&(*proot)->right, x);
  }
}

// See slide 23, chapter 8
Node *findNode(Node *root, int x) {
  if(root == NULL) {
    return NULL;
  }
  if(root->key == x) {
    return root;
  }
  if(root->key > x) {
    return findNode(root->left, x);
  } else {
    return findNode(root->right, x);
  }
}

// Deletes and returns as result the minimum node in the non-empty tree.
// Since the tree is non-empty, such minimum node must exist.
// This code is similar to findMin on slide 24, chapter 8, except that we do
// not have to test the NULL case since we know that the tree is non-empty.
Node *deleteMin(Node **proot) {
  if((*proot)->left == NULL) {
    // root is the minimum node, remove it from the tree and return it
    Node *minNode = *proot;
    *proot = (*proot)->right;
    return minNode;
  } else {
    // Keep moving down-left
    return deleteMin(&(*proot)->left);
  }
}

Node *deleteNode(Node **proot, int x){
  if(*proot == NULL) {
    // Cannot find key, deletion fails
    return NULL;
  }
  if((*proot)->key == x) {
    // Case 1: the node is a leaf
    // Note: this case is in fact a special case of the next one (case 2-a
    // or case 2-b) so this code could be merged with the next case.
    // We keep this case separate here for clarity.
    if((*proot)->left == NULL && (*proot)->right == NULL) {
      Node *deleted = *proot;
      *proot = NULL;
      return deleted;
    }
    // Case 2-a: the node has one left child
    if((*proot)->left != NULL && (*proot)->right == NULL) {
      Node *deleted = *proot;
      *proot = (*proot)->left;
      return deleted;
    }
    // Case 2-b: the node has one right child
    if((*proot)->left == NULL && (*proot)->right != NULL) {
      Node *deleted = *proot;
      *proot = (*proot)->right;
      return deleted;
    }
    // Case 3: the node has two children
    // We replace the root with the minimum node in the right subtree
    // (The maximum node in the left subtree would work too.)
    if((*proot)->left != NULL && (*proot)->right != NULL) {
      Node *deleted = *proot;
      // Find the minimum node in the right subtree:
      Node *minNode = deleteMin(&(*proot)->right);
      // Replace the root with the minNode:
      minNode->left = (*proot)->left;
      minNode->right = (*proot)->right;
      *proot = minNode;
      // Return the deleted node (the old root):
      return deleted;
    }
  }
  if((*proot)->key > x) {
    return deleteNode(&(*proot)->left, x);
  } else {
    return deleteNode(&(*proot)->right, x);
  }
}

void destroyTree(Node *root) {
  if(root == NULL) {
    return;
  }
  destroyTree(root->left);
  destroyTree(root->right);
  free(root);
}
